package com.hdu.other.monotonyStack;

public class lc907 {


    class Solution {
        public int sumSubarrayMins(int[] arr) {
            int p = 1000000007;
            int n = arr.length;
            int[] stack = new int[n];
            int r = 0;
            long ans = 0;
            for (int i = 0; i < n; i++) {
                if (r == 0 || arr[i] > arr[stack[r - 1]]) {
                    stack[r++] = i;
                }
                else {
                    while (r > 0 && arr[i] <= arr[stack[r - 1]]) {
                        int index = stack[--r];
                        /**
                         *
                         *   1      3     7
                         *   left  cur   i
                         *   [left + 1, cur - 1] cur  [cur + 1, i - 1]
                         *   2 3 4 5 6
                         *   (cur - left) * (i - cur)
                         */
                        int left = r == 0 ? -1 : stack[r - 1];
                        long curMinSum = (long) (index - left) * (i - index) * arr[index];
                        ans = (ans + curMinSum) % p;
                    }
                    stack[r++] = i;
                }
            }

            while (r > 0) {
                int index = stack[--r];
                int left = r == 0 ? -1 : stack[r - 1];
                long curMinSum = (long) (index - left) * (n - index) * arr[index];
                ans = (ans + curMinSum) % p;
            }

            return (int) ans;
        }
    }

}
